const nodes = [
  { id: 1, parentId: null },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 2 },
  { id: 5, parentId: 3 },
  { id: 6, parentId: 3 },
  { id: 7, parentId: 4 },
  { id: 8, parentId: 4 },
];

// 使用哈希表的方法 O(n)，其中 n 是节点的数量。 空间复杂度：O(n)
// function arrayToTree(list) {
//   const map = new Map(list.map((node) => [node.id, { ...node, children: [] }]));
//   console.log(map);
//   const tree = []
//   for (const node of map.values()) {
//     if (node.parentId === null) {
//       tree.push(node)
//     } else {
//       map.get(node.parentId).children.push(node)
//     }
//   }
//   return tree
// }
// console.log(JSON.stringify(arrayToTree(nodes)));
// console.log(arrayToTree(nodes));
// 使用递归 O(n^2)，其中 n 是节点的数量。 空间复杂度：O(n^2)。 优缺点：不适合大规模数据。
// function arrayToTreeRec (nodes, parentId = null) {
//   const result = []
//   for (const node of nodes) {
//     if (node.parentId === parentId) {
//       node.children = arrayToTreeRec(nodes, node.id)
//       console.log(arrayToTreeRec(nodes, node.id));
//       result.push(node)
//     }
//   }
//   return result
// }
// console.log(JSON.stringify(arrayToTreeRec(nodes,null)));
// 使用reduce
function arrayToTreeRedece (nodes) {
  const map = {}
  const tree = nodes.reduce((acc, node) => {
    map[node.id] = { ...node, children: [] };

    if (node.parentId === null) {
      acc.push(map[node.id]);
    } else {
      map[node.parentId].children.push(map[node.id]);
    }

    return acc;
  }, []);

  return tree;
}
console.log(JSON.stringify(arrayToTreeRedece(nodes)));
